package cn.dglydrpy.study.algorithm.learning.arraySort;

import cn.dglydrpy.study.algorithm.learning.utils.LogArithmometer;

import java.util.Arrays;

/**
 常数时间的操作:
 如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。称这样的操作为常数时间的操作。
 eg：
 常见的算术运算（+、-、*、/、% 等）
 常见的位运算（>>、>>>、<<、|、&、^等）
 赋值、比较、自增、自减操作等
 数组寻址操作

 总之，执行时间固定的操作都是常数时间的操作。反之，执行时间不固定的操作，都不是常数时间的操作。


 评估算法优劣的核心指标:
 1) 时间复杂度（流程决定）
 确定算法流程的总操作数量与样本数量之间的表达式关系,只看表达式最高阶项的部分
 常数项时间（实现细节决定）
 2) 额外空间复杂度（流程决定）
    


 如何确定算法流程的总操作数量与样本数量之间的表达式关系？
 1，想象该算法流程所处理的数据状况，要按照最差情况来。
 2，把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
 3，如果数据量为N，看看基本动作的数量和N是什么关系。

 当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。[N -> ∞ 时的极限]
 记为：O(忽略掉系数的高阶项)
 它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关。

 1，算法的过程，和具体的语言是无关的。
 2，想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉
 3，一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。
 这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。


 额外空间复杂度：
 你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。
 作为输入参数的空间，不算额外空间。
 作为输出结果的空间，也不算额外空间。
 因为这些都是必要的、和现实目标有关的。所以都不算。
 但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。
 如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。


 算法流程的常数项
 如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。
 此时：放弃理论分析，生成随机数据直接测。

 为什么不去理论分析？
 不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。
 比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。
 所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。


 一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，
 使用最少的空间的算法流程，叫这个问题的最优解。
 一般说起最优解都是忽略掉常数项这个因素的，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关

 排名从好到差：
 O(1)   
 O(logN)   
 O(N)   
 O(N*logN)   
 O(N^2)   O(N^3)   …   O(N^K)
 O(2^N)   O(3^N)   …   O(K^N)
 O(N!)


 算法和数据结构学习的大脉络
 1）知道怎么算的算法
 2）知道怎么试的算法
 
 */
public class Code01_ArraySort {

	/**
	 *  选择排序  O(n^2)
	 * @param arr
	 */
	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1  找到最小值，在哪，放到0位置上
		// 1 ~ n-1  找到最小值，在哪，放到1 位置上
		// 2 ~ n-1  找到最小值，在哪，放到2 位置上
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}

	/**
	 *  冒泡排序  O(n^2)
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1                max
		// 0 ~ N-2         max'
		// 0 ~ N-3  max''
		for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	/**
	 *  插入排序  O(n^2) 
	 * @param arr
	 */
	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 不只1个数
		for (int i = 1; i < arr.length; i++) { 
			
			// 0 ~ i 做到有序
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;

// 如何不用额外变量交换两个数?
/*
异或运算：相同为0，不同为1    无进位相加！
性质：
0^N == N  N^N == 0
异或运算满足交换律和结合率

!(a ^ b) 同或运算：相同为1，不同为0
*/
		
		
		// 这样也能完成交换，但注意i和j的值是一样的话，会出错！ 会变成0
//		arr[i] = arr[i] ^ arr[j];
//		arr[j] = arr[i] ^ arr[j];
//		arr[i] = arr[i] ^ arr[j];
	}
	
	


	/**
	 *
	 认识对数器
	 你在网上找到了某个公司的面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..
	 你和朋友交流面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..
	 你在网上做笔试，但是前几个测试用例都过了，突然一个巨大无比数据量来了，结果你的代码报错了，如此大的数据量根本看不出哪错了，你好心烦…

	 1，你想要测的方法a
	 2，实现复杂度不好但是容易实现的方法b
	 3，实现一个随机样本产生器
	 4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
	 5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a和方法b
	 6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。 
	 */
	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = LogArithmometer.generateRandomArray(maxSize, maxValue);
			int[] arr2 = LogArithmometer.copyArray(arr1);
			int[] arr3 = LogArithmometer.copyArray(arr1);
			int[] arr4 = LogArithmometer.copyArray(arr1);
			
			comparator(arr1);
			selectionSort(arr2);
			bubbleSort(arr3);
			insertionSort(arr4);
			
			if (!LogArithmometer.isEqual(arr1, arr2)) {
				succeed = false;
				System.out.println("selectionSort");
				LogArithmometer.printArray(arr1);
				LogArithmometer.printArray(arr2);
				break;
			}
			if (!LogArithmometer.isEqual(arr1, arr3)) {
				succeed = false;
				System.out.println("bubbleSort");
				LogArithmometer.printArray(arr1);
				LogArithmometer.printArray(arr3);
				break;
			}
			if (!LogArithmometer.isEqual(arr1, arr4)) {
				succeed = false;
				System.out.println("insertionSort");
				LogArithmometer.printArray(arr1);
				LogArithmometer.printArray(arr4);
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

	}
	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}



}
